package oj.oj_20;
// 有效的括号
//https://leetcode.cn/problems/valid-parentheses/
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();

        // 进行字符串中每个字符的遍历
        // 方法1
        // char[] array = s.toCharArray();
        // for (char c : array) {

        // }
        // 方法2
        // int len = s.length();
        // for (int i = 0; i < len; i++) {
        //     char c = s.charAt(i);
        // }

        char[] array = s.toCharArray();
        for (char c : array) {
            // 判断 c 是左括号还是右括号
            if (c == '(' || c == '[' || c == '{') {
                // 遇到了左括号，直接入栈
                stack.push(c);
            } else {
                // 题目明确了字符串中的所有字符一定是括号字符
                // 遇到了右括号
                // 1. 栈目前是不是空（empty）的
                if (stack.isEmpty()) {
                    // 遇到了一个没有左括号的右括号，不匹配
                    return false;
                }

                // 2. 再去判断栈顶元素；备注：isEmpty() 的判断必须先于取栈顶元素
                char left = stack.pop();    // 直接弹出
                if (!isMatch(left, c)) {
                    // 左右括号不匹配，说明整体匹配错误
                    return false;
                }
                // 3. 如果左右括号匹配了，继续处理下个字符
            }
        }

        // 所有的字符都遍历完成
        if (stack.isEmpty()) {
            // 所有的左括号都有对应的右括号
            return true;
        } else {
            // 左括号多出来了
            return false;
        }
    }

    private boolean isMatch(char left, char right) {
        if (left == '(') {
            return right == ')';
        }

        if (left == '[') {
            return right == ']';
        }

        // left 一定是 '{'
        return right == '}';
    }
}
